//==============================================================================
//
//            DGraph - the graph collection in the ofc-library
//
//               Copyright (C) 2005  Dick van Oudheusden
//  
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License as published by the Free Software Foundation; either
// version 2 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this library; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2005-07-10 09:02:12 $ $Revision: 1.1 $
//
//==============================================================================

#include "ofc/DGraph.h"

#include <float.h>


#if _INTERFACE_

#include "ofc/config.h"

#include "ofc/DList.h"

@class DGraphEdge;  // forward definition

//
// The graph node object stores an object in a node in a graph.
//

@interface DGraphNode : Object
{
@private
  DList         *_ingoing;    // the ingoing edges
  DList         *_outgoing;   // the outgoing edges
  DText         *_name;       // the name (set by DGraph)
  DText         *_label;      // the (graphviz) label
  DText         *_attributes; // the (graphviz) attributes
  id             _object;     // the stored object
  DGraphNode    *_prev;       // the previous node (during shortest path)
  double         _sum;        // the weight sum (during shortest path)
}


#endif



@implementation DGraphNode


//// Constructors

//
// Initialise an empty graph node
//
// @return the object
//
- (DGraphNode *) init
{
  [super init];
  
  _ingoing    = [DList new];
  _outgoing   = [DList new];

  _name       = [DText new];

  _label      = nil;
  _attributes = nil;
  
  _object     = nil;
  
  _prev       = nil;
  _sum        = DBL_MAX;
  
  return self;
}

//
// Initialise a graph node with a label and object
//
// @param label    the label for the node
// @param object   the object
//
// @return the object
//
- (DGraphNode *) init :(const char *) label :(id) object
{
  [self init];
  
  [self label  :label ];
  [self object :object];
  
  return self;
}

//
// Initialise a graph node with a label, attributes and object
//
// @param label        the label for the node
// @param attributes   the (graphviz) attributes for the node
// @param object       the object
//
// @return the object
//
- (DGraphNode *) init :(const char *) label :(const char *) attributes :(id) object
{
  [self init];
  
  [self label      :label ];
  [self attributes :attributes];
  [self object     :object];
  
  return self;
}


//// Copy related methods

//
// Deepen a copy of the graph node (not implemented)
//
// @return the object
//

- deepen
{
  WARNING(DW_METHOD_NOT_IMPL, "deepen");
  
  return self;
}


//// Destructor


//
// Free the graph node (the stored edges and object are NOT freed)
//
// @return the object
//
- shallowFree
{
  [_ingoing  shallowFree]; _ingoing  = nil;
  [_outgoing shallowFree]; _outgoing = nil;
  

  [_name free]; _name = nil;
  
  if (_label != nil)
  {
    [_label free]; _label = nil;
  }
  
  if (_attributes != nil)
  {
    [_attributes free]; _attributes = nil;
  }
  
  _object     = nil;
  _prev       = nil;  
  
  return [super free];
}

//
// Free the graph node (the stored object is freed, the stored 
// edges are NOT freed)
//
// @return the object
//
- free
{
  if (_object != nil)
  {
    [_object free]; _object = nil;
  }
  
  return [self shallowFree];
}


//// Member methods

//
// Return the name of the graph node (used by DGraph)
// 
// @return the name of the node
// 
- (const char *) name
{
  return [_name cstring];
}

//
// Set the name of the graph node (used by DGraph)
// 
// @param name    the name
// 
// @return the node object
// 
- (DGraphNode *) name :(const char *) name
{
  if ((name == NULL) || (*name == EOS))
  {
    WARNING(DW_INVALID_ARG, "name");
  }
  else
  {
    [_name set :name];
  }
  
  return self;
}

//
// Return the label of the graph node
//
// @return the label (or NULL)
//
- (const char *) label
{
  return (_label != nil) ? [_label cstring] : NULL;
}

//
// Set the label of the graph node
//
// @param label   the label (or NULL)
// 
// Return the node object
// 
- (DGraphNode *) label :(const char *) label
{
  if ((label == NULL) || (*label == EOS))
  {
    if (_label != nil)
    {
      [_label free]; _label = nil;
    }
  }
  else
  {
    if (_label == nil)
    {
      _label = [DText new];
    }
    
    [_label set :label];
  }
  
  return self;
}

//
// Return the (graphviz) attributes of the node
// 
// @return the attributes (or NULL)
// 
- (const char *) attributes 
{
  return (_attributes != nil) ? [_attributes cstring] : NULL;
}

//
// Set the (graphviz) attributes for the node
// 
// @param attributes    the attributes (or NULL)
// 
// @return the node object
// 
- (DGraphNode *) attributes :(const char *) attributes
{
  if ((attributes == NULL) || (*attributes == EOS))
  {
    if (_attributes != nil)
    {
      [_attributes free]; _attributes = nil;
    }
  }
  else
  {
    if (_attributes == nil)
    {
      _attributes = [DText new];
    }
    
    [_attributes set :attributes];
  }
  
  return self;
}

//
// Return the stored object in the node
// 
// @return the (stored) object (or nil)
// 
- (id) object
{
  return _object;
}

//
// Set the object for the node
// 
// @param object    the object (or nil)
// 
// @return the previous stored object
// 
- (id) object :(id) object
{
  id tmp = _object;
  
  _object = object;
  
  return tmp;
}


//// Path methods (used during shortest path determination)

//
// Reset the path
// 
// @return the node object
// 
- (DGraphNode *) path
{
  _prev = nil;
  _sum  = DBL_MAX;
  
  return self;
}

//
// Set the path 
// 
// @param prev    the previous node in the path
// @param sum     the sum of weights in the path
// 
// @return the node object
// 
- (DGraphNode *) path :(DGraphNode *) prev :(double) sum
{
  _prev = prev;
  _sum  = sum;
  
  return self;
}

//
// Return the previous node in the path
// 
// @return the previous node (or nil)
// 
- (DGraphNode *) prev
{
  return _prev;
}

//
// Return the sum of weights in the path
// 
// @return the sum
// 
- (double) sum
{
  return _sum;
}


//// Edge methods

//
// Return the ingoing degree of the node
// 
// @return the number of ingoing edges
// 
- (unsigned long) ingoingDegree
{
  return [_ingoing length];
}

//
// Return the outgoing degree of the node
// 
// @return the number of output edges
// 
- (unsigned long) outgoingDegree
{
  return [_outgoing length];
}

//
// Return the degree of the node
// 
// @return the number of ingoing and outgoing edges
// 
- (unsigned long) degree
{
  return [_ingoing length] + [_outgoing length];
}

//
// Add an ingoing edge
// 
// @param edge    the edge
// 
// @return the node object
// 
- (DGraphNode *) addIngoingEdge :(DGraphEdge *) edge
{
  if (edge == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "edge");
  }
  else if ([_ingoing has :edge])
  {
    WARNING(DW_UNKNOWN_WARNING, "edge already ingoing");
  }
  else
  {
    [_ingoing append :edge];
  }
  
  return self;
}

//
// Remove an ingoing edge
// 
// @param edge    the edge
// 
// @return success
// 
- (BOOL) removeIngoingEdge :(DGraphEdge *) edge
{
  BOOL ok = NO;
  
  if (edge == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "edge");
  }
  else
  {
    ok = [_ingoing remove :edge];
  }

  return ok;
}

//
// Add an outgoing edge
// 
// @param edge    the edge
// 
// @return the node object
// 
- (DGraphNode *) addOutgoingEdge :(DGraphEdge *) edge
{
  if ([_outgoing has :edge])
  {
    WARNING(DW_UNKNOWN_WARNING, "edge already outgoing");
  }
  else
  {
    [_outgoing append :edge];
  }
  
  return self;
}

//
// Remove an outgoing edge
// 
// @param edge    the edge
// 
// @return success
// 
- (BOOL) removeOutgoingEdge :(DGraphEdge *) edge
{
  BOOL ok = NO;
  
  if (edge == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "edge");
  }
  else
  {
    ok = [_outgoing remove :edge];
  }

  return ok;
}


//// Edge iterators

//
// Return the ingoing edge iterator
// 
// @return a (new) iterator on the ingoing edges
//
- (DListIterator *) ingoingEdges
{
  DListIterator *iter = [DListIterator alloc];
  
  [iter init :_ingoing];
  
  return iter;
}

//
// Return the outgoing edge iterator
// 
// @return a (new) list iterator on the outgoing edges
// 
- (DListIterator *) outgoingEdges
{
  DListIterator *iter = [DListIterator alloc];
  
  [iter init :_outgoing];
  
  return iter;
}

@end


  
  
#if _INTERFACE_

//
// The graph edge object stores an object in an edge of a graph.
//

@interface DGraphEdge : Object
{
@private
  DGraphNode    *_source;     // the source node
  DGraphNode    *_target;     // the target node
  DText         *_name;       // the name (set by DGraph)
  DText         *_label;      // the (graphviz) label 
  double         _weight;     // the weight of the edge (> 0.0)
  DText         *_attributes; // the (graphviz) attributes
  id             _object;     // the stored object
}
#endif


@implementation DGraphEdge


//// Constructors

//
// Initialise an empty graph edge
//
// @return the object
//
- (DGraphEdge *) init
{
  [super init];

  _name       = [DText new];
  
  _label      = nil;
  _attributes = nil;

  _weight     = 1.0;
  
  _source     = nil;
  _target     = nil;
  
  _object     = nil;
  
  return self;
}

//
// Initialise a graph edge with a label, weight and object
//
// @param label    the label
// @param weight   the weight (> 0.0)
// @param object   the object
//
// @return the object
//
- (DGraphEdge *) init :(const char *) label :(double) weight :(id) object
{
  [self init];
  
  [self label  :label ];
  [self weight :weight];
  [self object :object];
  
  return self;
}

//
// Initialise a graph edge with a label, weight, attributes and object
//
// @param label        the label 
// @param attributes   the (graphviz) attributes
// @param weight       the weight (> 0.0)
// @param object       the object
//
// @return the object
//
- (DGraphEdge *) init :(const char *) label :(const char *) attributes :(double) weight :(id) object
{
  [self init];
  
  [self label      :label ];
  [self weight     :weight];
  [self attributes :attributes];
  [self object     :object];
  
  return self;
}


//// Copy related methods

//
// Deepen a copy of the graph edge (not implemented)
//
// @return the object
//

- deepen
{
  WARNING(DW_METHOD_NOT_IMPL, "deepen");
  
  return self;
}


//// Destructor


//
// Free the graph edge (the stored object is NOT freed)
//
// @return the object
//
- shallowFree
{
  _source = nil;
  _target = nil;

  [_name free]; _name = nil;
  
  if (_label != nil)
  {
    [_label free]; _label = nil;
  }
 
  if (_attributes != nil)
  {
    [_attributes free]; _attributes = nil;
  }
  
  _object     = nil;
  
  return [super free];
}

//
// Free the graph edge (the stored object is freed)
//
// @return the object
//
- free
{
  if (_object != nil)
  {
    [_object free]; _object = nil;
  }
  
  return [self shallowFree];
}


//// Member methods

//
// Return the name of the edge (used by DGraph)
// 
// @return the name of the node
// 
- (const char *) name
{
  return [_name cstring];
}

//
// Set the name of the edge (used by DGraph)
// 
// @param name    the name
// 
// @return the edge object
// 
- (DGraphEdge *) name :(const char *) name
{
  if ((name == NULL) || (*name == EOS))
  {
    WARNING(DW_INVALID_ARG, "name");
  }
  else
  {
    [_name set :name];
  }
    
  return self;
}

//
// Return the (graphviz) label of the graph edge
//
// @return the label (or NULL)
//
- (const char *) label
{
  return (_label != nil) ? [_label cstring] : NULL;
}

//
// Set the (graphviz) label of the graph edge
//
// @param label   the label
// 
// Return the edge object
// 
- (DGraphEdge *) label :(const char *) label
{
  if ((label == NULL) || (*label == EOS))
  {
    if (_label != nil)
    {
      [_label free]; _label = nil;
    }
  }
  else
  {
    if (_label == nil)
    {
      _label = [DText new];
    }
    
    [_label set :label];
  }
  
  return self;
}

//
// Return the weight of the graph edge
//
// @return the weight
//
- (double) weight
{
  return _weight;
}

//
// Set the weight of the graph edge
//
// @param weight  the weight (> 0.0)
// 
// Return the edge object
// 
- (DGraphEdge *) weight :(double) weight
{
  if (weight <= 0.0)
  {
    WARNING(DW_INVALID_ARG, "double");
  }
  else
  {
    _weight = weight;
  }
  
  return self;
}

//
// Return the (graphviz) attributes of the edge
// 
// @return the attributes (or NULL)
// 
- (const char *) attributes 
{
  return (_attributes != nil) ? [_attributes cstring] : NULL;
}

//
// Set the (graphviz) attributes for the edge
// 
// @param attributes    the attributes
// 
// @return the edge object
// 
- (DGraphEdge *) attributes :(const char *) attributes
{
  if ((attributes == NULL) || (*attributes == EOS))
  {
    if (_attributes != nil)
    {
      [_attributes free]; _attributes = nil;
    }
  }
  else
  {
    if (_attributes == nil)
    {
      _attributes = [DText new];
    }
    
    [_attributes set :attributes];
  }
  
  return self;
}

//
// Return the stored object in the edge
// 
// @return the (stored) object (or nil)
// 
- (id) object
{
  return _object;
}

//
// Set the object for the edge
// 
// @param object    the object
// 
// @return the previous stored object
// 
- (id) object :(id) object
{
  id tmp = _object;
  
  _object = object;
  
  return tmp;
}


//// main methods

//
// Connect the source and target nodes by the edge
// 
// @param source    the source node (!= nil)
// @param target    the target node (!= nil)
// 
// @return success
// 
- (BOOL) connect :(DGraphNode *) source :(DGraphNode *) target
{
  BOOL ok = NO;
  
  if ((source == nil) || (target == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "source/target");
  }
  else
  {
    [self disconnect];
    
    
    _source = source;
    
    [_source addOutgoingEdge :self];


    _target = target;
    
    [_target addIngoingEdge :self];
    
    
    ok = YES;
  }
  
  return ok;
}

//
// Disconnect the edge from the source and target node
// 
// @return the edge object
// 
- (DGraphEdge *) disconnect 
{
  if (_source != nil)
  {
    [_source removeOutgoingEdge :self]; _source = nil;
  }
  
  if (_target != nil)
  {
    [_target removeIngoingEdge :self]; _target = nil;
  }

  return self;
}

//
// Return the source node
// 
// @return the source node
// 
- (DGraphNode *) source
{
  return _source;
}

//
// Return the target node
// 
// @return the target node (or nil)
// 
- (DGraphNode *) target
{
  return _target;
}

//
// Reverse the edge
// 
// @return the edge object
// 
- (DGraphEdge *) reverse
{
  DGraphNode *target = _source;
  DGraphNode *source = _target;

  [self connect :source :target];
  
  return self;
}
@end
  


#if _INTERFACE_

  
#include "ofc/DTextWritable.h"
  
//
// The graph collection stores objects in directed graph with nodes and edges. 
// Both the nodes as the edges can store objects. The graph collection can also 
// be used as graph data structure. Using the toDot method, the graph structure can 
// be exported to a dot-file which can be visualized with the software of 
// @link(www.graphviz.org). IMPORTANT: the node and edge objects are owned by the graph 
// object. Do NOT free them outside the scope of the graph object.
// 

@interface DGraph : Object
{
@private
  DList         *_nodes;       // the list with the graph nodes
  DList         *_edges;       // the list with the edges
  
  DText         *_attributes;  // the optional (graphviz) attributes
  
  long           _nodeCounter; // the node counter (for the node name)
  long           _edgeCounter; // the edge counter (for the edge name)
}
#endif


@implementation DGraph


//// Constructors

//
// Initialise an empty graph 
//
// @return the object
//
- (DGraph *) init
{
  [super init];
  
  _nodes       = [DList new];
  _edges       = [DList new];
  
  _attributes  = nil;

  _nodeCounter = 1;
  _edgeCounter = 1;
  
  return self;
}

//
// Initialise a graph with attributes 
//
// @param attributes   the (graphviz) attributes
//
// @return the object
//
- (DGraph *) init :(const char *) attributes
{
  [self init];
  
  [self attributes :attributes];
  
  return self;
}


//// Copy related methods

//
// Deepen a copy of the graph  (not implemented)
//
// @return the object
//

- deepen
{
  WARNING(DW_METHOD_NOT_IMPL, "deepen");
  
  return self;
}


//// Destructor

//
// Free the graph (the stored objects are NOT freed)
//
// @return the object
//
- shallowFree
{
  [_nodes each :@selector(shallowFree)];
  [_nodes shallowFree]; _nodes = nil;

  [_edges each :@selector(shallowFree)];
  [_edges shallowFree]; _edges = nil;
  
  if (_attributes != nil)
  {
    [_attributes free]; _attributes = nil;
  }
  
  return [super free];
}

//
// Free the graph  (the stored objects are freed)
//
// @return the object
//
- free
{
  [_nodes each :@selector(free)];
  [_nodes shallowFree]; _nodes = nil;

  [_edges each :@selector(free)];
  [_edges shallowFree]; _edges = nil;
  
  if (_attributes != nil)
  {
    [_attributes free]; _attributes = nil;
  }
  
  return [super free];
}


//// Member methods

//
// Return the (graphviz) attributes of the graph
// 
// @return the attributes (or NULL)
// 
- (const char *) attributes 
{
  return (_attributes != nil) ? [_attributes cstring] : NULL;
}

//
// Set the (graphviz) attributes for the graph
// 
// @param attributes    the attributes (or NULL)
// 
// @return the graph object
// 
- (DGraph *) attributes :(const char *) attributes
{
  if ((attributes == NULL) || (*attributes == EOS))
  {
    if (_attributes != nil)
    {
      [_attributes free]; _attributes = nil;
    }
  }
  else
  {
    if (_attributes == nil)
    {
      _attributes = [DText new];
    }
    
    [_attributes set :attributes];
  }
  
  return self;
}


//// Main methods

//
// Add a (new) node to the graph (graph is the owner of the node)
// 
// @param label       the label for the node (or NULL)
// @param attributes  the attributes for the node (or NULL)
// @param object      the object for the node (or nil)
// 
// @return the (new) node object
// 
- (DGraphNode *) addNode :(const char *) label :(const char *) attributes :(id) object
{
  DGraphNode *node = [DGraphNode alloc];

  [node init :label :attributes :object];

  [self addNode :node];
  
  return node;
}

//
// Add a (new) node to the graph (graph is the owner of the node)
// 
// @param node        the graph node
// 
// @return success
// 
- (BOOL) addNode :(DGraphNode *) node
{
  BOOL ok = NO;
  
  if (node == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "node");
  }
  else if ([_nodes has :node])
  {
    WARNING(DW_UNKNOWN_WARNING, "node already in graph");
  }
  else
  {
    DText *tmp = [DText new];
    
    [tmp format :"n%ld", _nodeCounter++];
    
    [node name :[tmp cstring]];
      
    [_nodes append :node];
    
    [tmp free];
    
    ok = YES;
  }
  
  return ok;
}

//
// Add a (new) edge to the graph (graph is the owner of the edge object)
// 
// @param label       the label for the edge (or NULL)
// @param attributes  the attributes for the edge (or NULL)
// @param weight      the weight for the edge
// @param object      the object for the edge (or nil)
// @param source      the source node
// @param target      the target node
// 
// @return the (new) edge object (or nil)
// 
- (DGraphEdge *) addEdge :(const char *) label :(const char *) attributes :(double) weight :(id) object :(DGraphNode *) source :(DGraphNode *) target
{
  DGraphEdge *edge = [DGraphEdge alloc];

  [edge init :label :attributes :weight :object];

  if (![self addEdge :edge :source :target])
  {
    // problems..
    [edge shallowFree]; edge = nil;
  }
  
  return edge;
}

//
// Add a (new) edge to the graph (graph is the owner of the edge object)
// 
// @param edge        the graph edge
// @param source      the source node 
// @param target      the target node
// 
// @return success
// 
- (BOOL) addEdge :(DGraphEdge *) edge :(DGraphNode *) source :(DGraphNode *) target
{
  BOOL ok = NO;
  
  if (edge == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "edge");
  }
  else if ([_edges has :edge])
  {
    WARNING(DW_UNKNOWN_WARNING, "edge already in graph");
  }
  else if ((source == nil) || (target == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "source/target");
  }
  else if (![_nodes has :source])
  {
    WARNING(DW_UNKNOWN_WARNING, "source not in graph");
  }
  else if (![_nodes has :target])
  {
    WARNING(DW_UNKNOWN_WARNING, "target not in graph");
  }
  else
  {
    {
      DText *tmp = [DText new];
    
      [tmp format :"e%ld", _edgeCounter++];
    
      [edge name :[tmp cstring]];
      
      [tmp free];
    }
  
    ok = [edge connect :source :target];

    if (ok)
    {
      [_edges append :edge];
    }
  }
  
  return ok;
}

//
// Reroute an existing edge in the graph
//  
// @param edge        the edge
// @param source      the new source for the edge
// @param target      the new target for the edge
// 
// @return success
// 
- (BOOL) reroute :(DGraphEdge *) edge :(DGraphNode *) source :(DGraphNode *) target
{
  BOOL ok = NO;
  
  if (edge == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "edge");
  }
  else if (![_edges has :edge])
  {
    WARNING(DW_UNKNOWN_WARNING, "edge not in graph");
  }
  else if ((source == nil) || (target == nil))
  {
    WARNING(DW_NIL_NOT_ALLOWED, "source/target");
  }
  else if (![_nodes has :source])
  {
    WARNING(DW_UNKNOWN_WARNING, "source not in graph");
  }
  else if (![_nodes has :target])
  {
    WARNING(DW_UNKNOWN_WARNING, "target not in graph");
  }
  else
  {
    ok = [edge connect :source :target];
  }
  
  return ok;
}

//
// Determine the shortest path between two nodes; a (new) list with REFERENCES
// to the nodes in the shortest path are returned; IMPORTANT: free this list 
// with shallowFree
// 
// @param from      the start node
// @param to        the end node
// @param weight    the destination for the path weight (or NULL)
// 
// @return a (new) list with REFERENCES to the nodes in the shortes path (or nil)
//
- (DList *) shortestPath :(double *) weight :(DGraphNode *) from :(DGraphNode *) to
{
  DList *path = nil;
  
  if ((from == nil) || (![_nodes has :from]))
  {
    WARNING(DW_INVALID_ARG, "from");
  }
  else if ((to == nil) || (![_nodes has :to]))
  {
    WARNING(DW_INVALID_ARG, "to");
  }
  else
  {
    DGraphNode *node  = from;
    DList      *todo  = [DList new];
    
    // Reset all nodes
    [_nodes each :@selector(path)];
    
    // Initialise the start node
    [node path :nil :0.0];
    
    // Process until the 'to' node is found or no more nodes can be processed
    while ((node != to) && (node != nil))
    {
      DListIterator *iter  = [node outgoingEdges];
      DGraphEdge    *edge  = nil;
      
      // Process all outgoing edges
      edge = [iter first];
      while (edge != nil)
      {
        DGraphNode *target = [edge target];

        if (target != nil)
        {
          double sum = [node sum] + [edge weight];
        
          if (sum < [target sum])
          {
            [target path :node :sum];
          
            // Add target node if not already there
            if (![todo has :target])
            {
              [todo append :target];
            }
          }
        }
        
        edge = [iter next];
      }
      [iter free];
      
      // Determine the node with the lowest sum for next processing
      {
        DGraphNode *walk = nil;
        double      sum  = DBL_MAX;
        
        iter = [DListIterator alloc];
        
        [iter init :todo];
        
        node = nil;
        walk = [iter first];
        while (walk != nil)
        {
          if ([walk sum] < sum)
          {
            node = walk;
            sum  = [walk sum];
          }
          walk = [iter next];
        }
        [iter free];
        
        if (node != nil)
        {
          [todo remove :node];
        }
      }
    }
    [todo shallowFree];
    
    if (node == to)
    {
      if (weight != NULL)
      {
        *weight = [to sum];
      }
      
      // fill nodes with the shortest path
      path = [DList new];
     
      node = to;
      do
      {
        [path prepend :node];
        
        node = [node prev];
      }
      while (node != nil);
    }
  }
  
  return path;
}

//
// Check if the graph has a node
// 
// @param node      the graph node
// 
// @return has it ?
// 
- (BOOL) hasNode :(DGraphNode *) node
{
  return ((node != nil) && ([_nodes has :node]));
}

//
// Check if the graph has an edge
// 
// @param edge      the graph edge
// 
// @return has it ?
// 
- (BOOL) hasEdge :(DGraphEdge *) edge
{
  return ((edge != nil) && ([_edges has :edge]));
}

//
// Remove an node from the graph (node must be unconnected)
// 
// @param node      the graph node
// 
// @return the object stored in the node (or nil)
// 
- (id) removeNode :(DGraphNode *) node
{
  id object = nil;
  
  if (node == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "node");
  }
  else if ([node degree] > 0)
  {
    WARNING(DW_UNKNOWN_WARNING, "node still connected");
  }
  else
  {
    if ([_nodes remove :node])
    {
      object = [node object];
      
      [node shallowFree];
    }
    else
    {
      WARNING(DW_UNKNOWN_WARNING, "node not in graph");
    }
  }
  
  return object;
}

//
// Remove an edge from the graph (auto disconnect)
// 
// @param edge      the edge node
// 
// @return the object stored in the edge (or nil)
// 
- (id) removeEdge :(DGraphEdge *) edge
{
  id object = nil;
  
  if (edge == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "edge");
  }
  else if (![_edges has :edge])
  {
    WARNING(DW_UNKNOWN_WARNING, "edge not in graph");
  }
  else
  {
    if (([edge source] != nil) || ([edge target] != nil))
    {
      [edge disconnect];
    }
    
    if ([_edges remove :edge])
    {
      object = [edge object];
      
      [edge shallowFree];
    }
  }
  
  return object;
}


//// Iterators

//
// Return a (new) iterator on all the nodes in the graph
// 
// @return a (new) iterator
// 
- (DListIterator *) nodes
{
  DListIterator *iter = [DListIterator alloc];
  
  [iter init :_nodes];
  
  return iter;
}

//
// Return a (new) iterator on all the edges in the graph
// 
// @return a (new) list iterator
// 
- (DListIterator *) edges
{
  DListIterator *iter = [DListIterator alloc];
  
  [iter init :_edges];
  
  return iter;
}


//// Export methods

//
// Export to DOT 
// 
// @param writer    the output object
// 
// @return success ?
// 
- (BOOL) toDot :(id <DTextWritable>) writer
{
  BOOL ok = NO;
  
  if (writer == nil)
  {
    WARNING(DW_NIL_NOT_ALLOWED, "writer");
  }
  else
  {
    DListIterator *iter = nil;
    DGraphEdge    *edge = nil;
    DGraphNode    *node = nil;

    
    ok  = [writer writeLine :"digraph G {"];
    
    if ([self attributes] != NULL)
    {
      ok &= [writer writeLine :"  /* the graph attributes */"];
      ok &= [writer writeText :"  "];
      ok &= [writer writeText :[self attributes]];
      ok &= [writer writeLine :";"];
    }
    
    
    ok &= [writer writeLine :"  /* the edges */"];
    
    iter = [self edges];
    
    edge = [iter first];
    
    while (edge != nil)
    {
      if (([edge source] != nil) && ([edge target] != nil))
      {
        const char *edgeLabel = [edge label];
        const char *edgeAttr  = [edge attributes];
        
        // add the edge
        ok &= [writer writeText :"  "]; // ident
        ok &= [writer writeText :[[edge source] name]];
        ok &= [writer writeText :" -> "];
        ok &= [writer writeText :[[edge target] name]];
        
        // add the edge label and/or attributes
        if ((edgeLabel != NULL) || (edgeAttr != NULL))
        {
          ok &= [writer writeText :" ["];
          
          if (edgeLabel != NULL)
          {
            ok &= [writer writeText :"label=\""];
            ok &= [writer writeText :edgeLabel];
            ok &= [writer writeText :"\""];
          }
          
          if ((edgeLabel != NULL) && (edgeAttr != NULL))
          {
            ok &= [writer writeText :","];
          }
          
          if (edgeAttr != NULL)
          {
            ok &= [writer writeText :edgeAttr];
          }
          
          ok &= [writer writeText :"]"];
        }
        
        ok &= [writer writeLine :";"];
      }
      
      edge = [iter next];
    }
    [iter free];
    

    ok &= [writer writeLine :"/* the node attributes */"];

    iter = [self nodes];
    
    node = [iter first];
    
    while (node != nil)
    {
      const char *nodeLabel = [node label];
      const char *nodeAttr  = [node attributes];
      
      if ((nodeLabel != NULL) || (nodeAttr != NULL))
      {
        // add the node
        ok &= [writer writeText :"  "]; // ident
        ok &= [writer writeText :[node name]];
        
        // add the node label and/or the attributes
        ok &= [writer writeText :" ["];
          
        if (nodeLabel != NULL)
        {
          ok &= [writer writeText :"label=\""];
          ok &= [writer writeText :nodeLabel];
          ok &= [writer writeText :"\""];
        }
          
        if ((nodeLabel != NULL) && (nodeAttr != NULL))
        {
          ok &= [writer writeText :","];
        }
          
        if (nodeAttr != NULL)
        {
          ok &= [writer writeText :nodeAttr];
        }
          
        ok &= [writer writeText :"]"];
      }
      
      node = [iter next];
    }
    [iter free];
    
    ok &= [writer writeLine :"}"];
  }
  return ok; 
}

@end

/*==========================================================================*/
